package binarySearch;

public class searchMatrix {
    // public boolean searchMatrix(int[][] matrix, int target) {
    //     //确定横坐标
    //     int[] arrX = new int[matrix.length];
    //     for(int i =0;i<matrix.length;i++){
    //         arrX[i]=matrix[i][0];
    //     }
    //     int x = binarySearch(arrX, target);
    //     //越界判断
    //     if (x<0||x>=arrX.length) {
    //         return false;
    //     }
    //     if (matrix[x][0]==target) {
    //         return true;
    //     }else{
    //         int rs = binarySearch(matrix[x], target);
    //         if (matrix[x][rs]==target) {
    //             return true;
    //         }
    //     }
    //     return false;
    // }
    // public int binarySearch(int[] matrix, int target){
    //     //一开始范围设置错了
    //     int left=0,right=matrix.length-1;
    //     int mid=0;
    //     while (left<=right) {
    //         mid=(left+right)/2;
    //         if (matrix[mid]==target) {
    //             return mid;
    //         }else if (matrix[mid]>target) {
    //             right=mid-1;
    //         }else{
    //             left=mid+1;
    //         }
    //     }
    //     return left-1;
    // }
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] arr = new int[matrix.length];
        for(int i =0;i<matrix.length;i++){
            arr[i]=matrix[i][0];
        }
        int first = firstsmaller(arr,target);
        if(first==-1){
            //没有比我小的
            return false;
        }
        int rs =binarysearch(matrix[first],target);
        return rs!=-1;
    }
    public int firstsmaller(int[] arr,int target){
        int left=0,right=arr.length-1;
        int ans=-1,mid=0;
        while(left<=right){
            mid=(left+right)/2;
            if(arr[mid]>target){
                right=mid-1;
            }else{
                ans=mid;
                left=mid+1;

            }
        }
        
        
        return ans;
    }
    public int binarysearch(int[] arr,int target){
        int left=0,right=arr.length-1;
        int mid=0;
        while(left<=right){
            mid=(left+right)/2;
            if(arr[mid]>target){
                right=mid-1;

            }else if(arr[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        // int[][] arr = new int[][]{
        //     {1,3,5,7},
        //     // {10,11,16,20},
        //     // {23,30,34,60},
        // };
        int[][] arr = new int[][]{
            {1},{3},{5}
            
        };
        //只有一行or只有一列
        searchMatrix obj = new searchMatrix();
        System.out.println(obj.searchMatrix(arr, 3));
    }
}
